use std::cell::RefCell;
use std::rc::Rc;
// 输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
// 输出：[5,5,2,5,4,5,6,7]


#[derive(Debug, PartialEq, Eq)]
pub struct LinkNode {
  pub val: usize,
  pub links: Vec<Rc<RefCell<LinkNode>>>,
}

impl LinkNode {
  #[inline]
  pub fn new(val: usize) -> Self {
    LinkNode {
      val,
      links: vec![],
    }
  }
}

struct Solution {}

impl Solution {
  pub fn loud_and_rich(richer: Vec<Vec<i32>>, quiet: Vec<i32>) -> Vec<i32> {
    let len = quiet.len();
    let mut link_map = vec![];
    for i in 0..len {
      link_map.push(Rc::new(RefCell::new(LinkNode::new(i))));
    }
    for pair in richer.iter() {
      link_map[pair[1] as usize].borrow_mut().links.push(Rc::clone(&link_map[pair[0] as usize]));
    }
    let mut global = vec![-1; len];
    fn find_max(node: Rc<RefCell<LinkNode>>, quiet: &Vec<i32>, global: &mut Vec<i32>) -> i32 {
      let curr = node.borrow();
      if global[curr.val] != -1 {
        return global[curr.val];
      }
      let mut vals = vec![];
      vals.push(curr.val as i32);
      for i in &curr.links {
        vals.push(find_max(i.clone(), quiet, global))
      }
      if let Some(ret) = vals.iter().reduce(|a, b| {
        if quiet[*a as usize] < quiet[*b as usize] {
          return a;
        }
        b
      }) {
        global[curr.val] = *ret as i32;
        return *ret as i32;
      }
      global[curr.val]=vals[0];
      vals[0]
    }
    for (i,node) in link_map.iter().enumerate() {
      if global[i] == -1 {
        global[i] = find_max(node.clone(), &quiet, &mut global);
      }
    }
    return global; 
  }
}